import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(c == '{' || c == '[' || c == '('){
                stack.push(c);
            }
            else{
                if(stack.isEmpty()) return false;
                char last = stack.pop();
                if(!match(last, c)) return false;
            }
        }
        if(stack.isEmpty()) return true;
        return false;
    }

    boolean match(char l, char r){
        return l == '(' && r == ')' || l == '[' && r == ']' || l == '{' && r == '}';
    }
}